package problem22;

//22.括号生成
//https://leetcode.cn/problems/generate-parentheses/

import java.util.ArrayList;
import java.util.List;

class Solution {
    private int n;
    List<String> list = new ArrayList<>();

    // k:左括号的数量
    private void dfs(int k, StringBuffer str) {
        //如果右括号的数量大于左括号||左括号的数量>n 剪枝
        if(str.length() - k > k || k > n) return;

        if(str.length() == n*2 ) {
            list.add(new String(str));
            return;
        }
        //添加左括号
        if(k < n) {
            str.append("(");
            dfs(k+1, str);
            str.deleteCharAt(str.length()-1);
        }
        //添加右括号
        if(str.length() - k < k) {
            str.append(")");
            dfs(k, str);
            str.deleteCharAt(str.length()-1);
        }
    }
    public List<String> generateParenthesis (int _n) {
        n = _n;
        dfs(0, new StringBuffer());
        return list;
    }
}